from calc import is_square
from pythagoras import triple_gen2
from itertools import count, izip

def is_solution(x, y, z):
    d1 = (x + y) ** 2 + z ** 2
    d2 = (x + z) ** 2 + y ** 2
    d3 = (y + z) ** 2 + x ** 2
    
    return is_square(min(d1, d2, d3))

def triples(limit):
    result = set();
    
    for (a,b,c) in triple_gen2(limit):
        for n in count(1):
            if n*a < limit and n*b < limit:
                result.add((n*a, n*b, n*c))
            else:
                break
    
    return result

pt_limit = 4000
pt = triples(pt_limit)
print "Found:",len(pt),"pythagorean triples with a and b <",pt_limit

solutions = set()
for (a, b, c) in pt:
    for i in xrange(1, a/2 + 1):
        p = sorted([i, a-i, b])
        if is_solution(p[0], p[1], p[2]):
            solutions.add((p[0], p[1], p[2]))
    
    for i in xrange(1, b/2 + 1):
        p = sorted([a, i, b-i])
        if is_solution(p[0], p[1], p[2]):
            solutions.add((p[0], p[1], p[2]))
        
print "Found:",len(solutions),"solutions"

def nr_solutions(limit):
    return sum(1 for (x,y,z) in solutions if z <= limit and y <= z and x <= y)

min = 1500
max = 2000

while min + 1 < max:
    middle = (min + max + 1) / 2
    n = nr_solutions(middle)
    print middle, n
    if n < 1000 * 1000: min = middle
    else: max = middle
    
exit()

print sorted((x,y,z) for (x,y,z) in paths if z <= 10 and y <= z and x <= y)

print sorted(set((x,y,z) for z in xrange(1,11)
                 for y in xrange(1,z+1)
                 for x in xrange(1,y+1)
                 if is_solution(x,y,z)))
        
                  
    
        

